package pro.softzhang.algo.lc100;

import pro.softzhang.algo.common.TreeNode;

import java.util.*;

/**
 * 103. 二叉树的锯齿形层序遍历
 * https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
 */
public class LC103_BinaryTreeZigzagLevelOrderTraversal {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) {
                return result;
            }

            List<TreeNode> currentNodes = new ArrayList<TreeNode>(){{
                add(root);
            }};

            // int flag = 0;
            while (!currentNodes.isEmpty()) {
                List<TreeNode> nextNodes = new ArrayList<>();
                List<Integer> levelVals = new ArrayList<>();
                for (TreeNode node : currentNodes) {
                    levelVals.add(node.val);
                    if (node.left != null) {
                        nextNodes.add(node.left);
                    }
                    if (node.right != null) {
                        nextNodes.add(node.right);
                    }
                }

                // 搞完一层
                // flag++;

                currentNodes = nextNodes;
                if (result.size() % 2 == 1) {
                    Collections.reverse(levelVals);
                }

                result.add(levelVals);
            }
            return result;
        }
    }

    static
    class Solution1 {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) {
                return result;
            }

            Queue<TreeNode> currentNodes = new LinkedList<TreeNode>(){{
                offer(root);
            }};

            while (!currentNodes.isEmpty()) {
                List<Integer> levelVals = new ArrayList<>();

                int queueSize = currentNodes.size();
                while (queueSize-- > 0) {
                    TreeNode node = currentNodes.poll();
                    levelVals.add(node.val);
                    if (node.left != null) {
                        currentNodes.offer(node.left);
                    }
                    if (node.right != null) {
                        currentNodes.offer(node.right);
                    }
                }

                if (result.size() % 2 == 1) {
                    Collections.reverse(levelVals);
                }

                result.add(levelVals);
            }
            return result;
        }
    }
}
